package lower_bound;

require Exporter;
use strict;
use warnings;


our @ISA = qw(Exporter);
our $VERSION = 1.00;
our @EXPORT = qw(	
					upper_bound
					lower_bound
				);


sub lower_bound(\@$$$)
{
	my ($val, $test, $first, $last) = @_;
	$first = 0 unless (defined $first);
	$last = @$val unless (defined $last);
	my $len = $last - $first;
	my $half;
	my $mid;
	while ($len > 0)
	{
		$half = int ($len / 2);
		$mid = $first + $half;
		if ($val->[$mid] < $test)
		{
			$first = $mid + 1;
			$len = $len - $half - 1
		}
		else
		{
			$len = $half
		}
	}
	return $first;
}

sub upper_bound(\@$$$)
{
	my ($val, $test, $first, $last) = @_;
	$first = 0 unless (defined $first);
	$last = @$val unless (defined $last);
	my $len = $last - $first;
	#print ("$first $last, $len\n");
	my $half;
	my $mid;
	while ($len > 0)
	{
		$half = int ($len / 2);
		$mid = $first + $half;
		#print "half = $half\nmid = $mid\nfirst = $first\n\n";
		if ($val->[$mid] <= $test)
		{
			$first = $mid + 1;
			$len = $len - $half - 1
		}
		else
		{
			$len = $half
		}
	}
	return $first;
}

